package com.pw.study.structure.arr;

/**
 * @Desc: 稀疏数组
 * @author: future
 * @since: 2022/10/20-23:24
 */
public class SparseArray {
    public static void main(String[] args) {
        //1.初始化数组
        int[][] arr = initArr();
        //2.数组赋值
        addValueArray(arr);
        //3.统计记录
        int[][] sparseArr = countArrAndCreateSparseArr(arr);
        //4.稀疏数组还原
        int[][] chess = dealSparseArrToChess(sparseArr);
        printArr(arr);
        printArr(sparseArr);
        printArr(chess);

    }

    private static int[][] dealSparseArrToChess(int[][] sparseArr) {
        int col = sparseArr[0][0];
        int row = sparseArr[0][1];
        int size = sparseArr[0][2];

        int[][] arr = new int[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                arr[i][j] = 0;
            }
        }
        for (int i = 1; i < size+1; i++) {
            arr[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
        }

        return arr;
    }

    /**
     * 统计数据，并记录到稀疏表中
     *
     * @param arr
     * @return
     */
    private static int[][] countArrAndCreateSparseArr(int[][] arr) {
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length; j++) {
                if (arr[i][j] != 0) {
                    sum = sum + 1;
                }
            }
        }
        int[][] sparseArr = new int[sum + 1][3];
        sparseArr[0][0] = 11;
        sparseArr[0][1] = 11;
        sparseArr[0][2] = sum;
        int k = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length; j++) {
                if (arr[i][j] != 0) {
                    k++;
                    sparseArr[k][0] = i;
                    sparseArr[k][1] = j;
                    sparseArr[k][2] = arr[i][j];
                }
            }
        }

        return sparseArr;
    }

    /**
     * 数组赋值
     *
     * @param arr
     */
    private static void addValueArray(int[][] arr) {
        arr[1][2] = 1;
        arr[4][5] = 2;
        arr[3][6] = 1;
        arr[7][8] = 2;
    }

    /**
     * 打印数组
     *
     * @param arr
     */
    private static void printArr(int[][] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                System.out.print(arr[i][j] + " ");
            }
            System.out.println();
        }
    }

    /**
     * 初始化数组
     *
     * @return
     */
    private static int[][] initArr() {
        int[][] arr = new int[11][11];
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                arr[i][j] = 0;
            }
        }
        return arr;
    }

}
